/*--- shell.c ----------------------------- Listing 5-6 ---------
 * Shell's sort on an array
 *
 * #define DRIVER to compile a test driver
 * Driver must be linked to sortsub.c (Listing 5-1)
 *-------------------------------------------------------------*/

#include "sorthdr.h"

#define DRIVER 1

void ShellSort(Element **Array, int N, CompFunc Compare)
{
    int step, h;

    /* Find starting h */
    for (h = 1; h <= N / 9; h = 3*h + 1)
        ;

    /* Now loop thru successively smaller h's */
    for ( ; h > 0; h /= 3) {
        /* Look at hth thru Nth elements */
        for (step = h; step < N; step++) {
            int i;
            Element *temp;

            /* Now, look to the left and find our spot */
            temp = Array[step];
            for (i = step - h; i >= 0; i -= h) {
                if (Compare(temp, Array[i]) < 0) {
                    /* Not there yet, so make room */
                    Array[i + h] = Array[i];
                } else      /* Found it! */
                    break;
            }
            /* Now insert original value from Array[step] */
            Array[i + h] = temp;
        }
    }
}

#ifdef DRIVER
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "sortsub.h"

/*
 * A comparison function
 */
int Cfunc(Element *L, Element *R)
{
    return (strncmp(L->text, R->text, 5));
}

void main(int argc, char *argv[])
{
    Element **Array;
    int Items = 2000;

    if (argc != 2 && argc != 3) {
        fprintf(stderr, "Usage: shell infile [maxitems]\n");
        return;
    }

    if (argc == 3)
        Items = atoi(argv[2]);

    if ((Items = LoadArray(argv[1], Items, &Array)) == -1)
        return; /* Couldn't load file */

    ShellSort(Array, Items, (CompFunc)Cfunc);
    ShowArray(Array, Items, (CompFunc)Cfunc);
}
#endif
